package day37_438;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @ClassName Solution
 * @Description 哈希表+滑动窗口
 * @Author clockTown
 * @Date 2021/6/15 19:43
 * @Version 1.0
 */
public class Solution1 {
    public static List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> res = new ArrayList<>();

        if (s == null || p == null || s.length() < p.length()){
            return res;
        }

        //存储p字符串的字母数量
        int[] ch = new int[26];
        for (char c : p.toCharArray()) {
            ch[c - 'a']++;
        }

        //窗口左右边界
        int l = 0, r = 0, rest = p.length();
        //构建第一个滑动窗口
        for (; r < p.length(); r++) {
            ch[s.charAt(r) - 'a']--;
            if (ch[s.charAt(r) - 'a'] >= 0){
                rest --;
            }
        }
        if (rest == 0){
            res.add(0);
        }

        //开始滑动
        while (r < s.length()) {
            //弹出左边元素
            char temp = s.charAt(l);
            if (ch[temp - 'a'] >= 0){
                rest ++;
            }
            ch[temp - 'a']++;
            l++;

            //右边元素
            temp = s.charAt(r);
            ch[temp - 'a']--;
            if (ch[temp - 'a'] >= 0){
                rest --;
            }
            r++;

            //判断
            if (rest == 0){
                res.add(l);
            }
        }

        return res;

    }
}
